/**
 * 给定数组，要求从中选取K个互不相同的子数组，使得极差之和最大
 * 如果子数组A完全包含子数组B，则子数组A的极差必然不小
 * 令Si表示以[i,n-1]子数组，即以i开头直到结束的子数组
 * 使用优先级队列维护这N个子数组，取出当前元素记作{v, s, e}
 * 则将{x, s, e - 1}插入队列
 * 因此队列中总是维护当前所有开头位置的子数组，当前极差最大的子数组一定在队列中
 * 需要快速求出[s, e]区间的极差，可以使用SparseTable
 * O(NlogN + KlogN)
 */
template<typename IT = vector<int>::const_iterator>
struct SparseTable{

using T = pair<int, int>;
using vt = vector<T>; 
using vvt = vector<vt>;

SparseTable() = delete;

IT head;
vvt data;

/// 从s开始的n个数，作为原始数组，建立ST表，索引从0开始
/// 整个ST期间，原始数组的内容不能改变
SparseTable(IT begin, int n):head(begin){
    data.assign(n, vt());

    for(int i=0;i<n;++i) {
		data[i].reserve(21); // 100w用21即可
		data[i].emplace_back(i, i);
	}

	for(int j=1,t;(t=1<<j)<=n;++j){
        for(int i=0;i+t<=n;++i){
			const auto & prv = data[i][j-1];
			const auto & nxt = data[i+(t>>1)][j-1];

			auto first = *(begin + prv.first) <= *(begin + nxt.first) ? prv.first : nxt.first;
			auto second = *(begin + nxt.second) <= *(begin + prv.second) ? prv.second : nxt.second;

			data[i].emplace_back(first, second);
		} 
	}

	return;
}

/// 查询[s, e]区间的极小极大值所在的下标，即距离构造函数begin的偏移量
/// 索引从0开始
T query(int s, int e)const{
    int k = static_cast<int>(log2((double)(e - s + 1)));
	const auto & p1 = data[s][k];
	const auto & p2 = data[e-(1<<k)+1][k];
    return {
        *(head + p1.first) <= *(head + p2.first) ? p1.first : p2.first,
		*(head + p2.second) <= *(head + p1.second) ? p1.second : p2.second 
	};
}


};

struct _t{
    int v;
    int left;
    int right;
    bool operator < (const _t & rhs) const {
        if(v != rhs.v) return v < rhs.v;
        if(left != rhs.left) return left < rhs.left;
        return right < rhs.right;
    }
};

class Solution {

using llt = long long;

public:
    long long maxTotalValue(vector<int>& nums, int k) {
        SparseTable<> st(nums.begin(), nums.size());

        int n = nums.size();
        priority_queue<_t> q;
        for(int i=0;i<n;++i){
            auto p = st.query(i, n - 1);
            q.push({nums[p.second] - nums[p.first], i, n - 1});
        }

        llt ans = 0;
        for(int i=0;i<k;++i){
            auto h = q.top(); q.pop();
            ans += h.v;
            
            auto left = h.left;
            auto right = h.right - 1;
            if(left <= right){
                auto p = st.query(left, right);
                q.push({nums[p.second] - nums[p.first], left, right});
            }
        }
        return ans;
    }
};
